<!DOCTYPE html>
<html lang="en">
<head>
  <meta charset="UTF-8">
  <meta name="viewport" content="width=device-width, initial-scale=1.0">
  <title>数据结构之图</title>
</head>
<body>
  <script type="text/javascript">
    function Graph(v) {
      this.vertices = v; // 顶点
      this.edges = 0; // 边的数量
      this.adj = []; // 邻接表
      this.marked = []; // 存储顶点的状态，是否被访问过
      // 创建二维数组，邻接表是一个二维数组
      for (var i = 0; i < this.vertices; i++) {
        this.adj[i] = [];
        this.marked[i] = false;
      }
      this.shortestPath = []; // 用一个数组来记录最短路径所有的边
      this.hasPath = hasPath; // 判断是否有路径
      this.findShortestPath = findShortestPath; // 寻找最短路径
      this.addEdge = addEdge; // 添加边
      this.showGraph = showGraph; // 打印图
      this.dfs = dfs; // 深度优先搜索
      this.bfs = bfs; // 广度优先搜索
    }

    // 添加边，参数是两个顶点
    function addEdge(v, w) {
      this.adj[v].push(w);
      this.adj[w].push(v);
      this.edges++;
    }

    // 打印图，其实就是打印邻接表
    function showGraph() {
      for (var i = 0; i < this.vertices; i++) {
        var edges = '';
        for (var j = 0; j < this.vertices; j++) {
          // 判断两个顶点之间是否有边
          if (this.adj[i][j]) {
            edges += this.adj[i][j] + ' ';
          }
        }
        console.log(i + '->' + edges);
      }
    }

    // 深度优先搜索
    function dfs(v) {
      // 标记初始顶点已经被访问过
      this.marked[v] = true;
      // 如果该顶点在邻接表中有值，说明图中有与之相连的边，可以打印该顶点
      if (this.adj[v]) {
        console.log('深度优先搜索结果：顶点 ' + v + ' 已经被访问过了！');
      }
      // 遍历跟该顶点项相连的其他顶点
      for (var w in this.adj[v]) {
        var current = this.adj[v][w];
        // 如果当前顶点没被访问过
        if (!this.marked[current]) {
          // 递归遍历
          this.dfs(current);
        }
      }
    }

    // 广度优先搜索
    function bfs(v) {
      var queue = []; // 队列
      this.marked[v] = true; // 标记初始顶点已经被访问过
      queue.push(v); // 将访问过的顶点放入队列中
      while (queue.length > 0) {
        var q = queue.shift(); // 逐个出列，并寻找与出列顶点相连的其他顶点
        if (q !== undefined) {
          console.log('广度优先搜索结果：顶点 ' + q + ' 已经被访问过了！');
        }
        // 遍历与出列顶点相连的其他顶点
        for (var w in this.adj[q]) {
          var current = this.adj[q][w];
          // 如果当前节点没被访问过
          if (!this.marked[current]) {
            this.marked[current] = true; // 标记为以访问
            this.shortestPath[current] = q; // 说明有一条边可以从 current 顶点到 q 顶点
            queue.push(current); // 并将该顶点放入队列中
          }
        }
      }
    }

    // 判断是否有路径
    function hasPath(v) {
      // 如果当前顶点有被访问，说明就有路径
      return this.marked[v];
    }

    // 寻找最短路径，它的实现是基于广度优先搜索的
    function findShortestPath(v) {
      var source = 0;
      if (!this.hasPath(v)) {
        return undefined;
      }
      var path = [];
      for (var i = v; i !== source; i = this.shortestPath[i]) {
        path.push(i);
      }
      path.push(source);
      return path;
    }

    var graph = new Graph(5);
    graph.addEdge(0, 1);
    graph.addEdge(0, 2);
    graph.addEdge(1, 3);
    graph.addEdge(2, 4);
    graph.showGraph();
    // graph.dfs(0);
    graph.bfs(0);
    var paths = graph.findShortestPath(4); // 寻找从顶点0到顶点4的最短路径
    // 方便展示最短路径
    var str = '';
    while (paths.length) {
      if (paths.length > 1) {
        str += paths.pop() + '->';
      } else {
        str += paths.pop();
      }
    }
    console.log(str);
  </script>
</body>
</html>